package org.example.acm;

import java.util.Scanner;

public class CountDistinctStringsSolution {
    private int count = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        char[] chars = input[0].toCharArray();
        int n = Integer.parseInt(input[1]);
        CountDistinctStringsSolution solution = new CountDistinctStringsSolution();
        System.out.println(solution.calCount(chars, n));
        scanner.close();
    }

    public int calCount(char[] chars, int n) {
        char[] item = new char[n];
        boolean[] used = new boolean[chars.length];
        dfs(chars, n, 0, item, used);
        return count;
    }

    private void dfs(char[] chars, int n, int len, char[] item, boolean[] used) {
        if (len == n) {
            count++;
            return;
        }
        Character lastUse = null;
        for (int j=0;j<chars.length;j++) {
            if (!used[j]
                    && (len == 0 || item[len-1] != chars[j])
                    && (lastUse == null || lastUse != chars[j])) {
                used[j] = true;
                lastUse = chars[j];
                item[len] = chars[j];
                dfs(chars, n, len+1, item, used);
                used[j] = false;
            }

        }
    }
}
